// https://www.lintcode.com/problem/hash-function/

public class Solution {
    /**
     * @param key: A string you should hash
     * @param HASH_SIZE: An integer
     * @return: An integer
     */
    public int hashCode(char[] key, int HASH_SIZE) {
        // write your code here
        long ret = 0, value = 1;
        for (int i = key.length -1; i >= 0; --i) {
            ret += (Integer.valueOf(key[i]) * value) % HASH_SIZE;
            ret %= HASH_SIZE;
            value = (value * 33) % HASH_SIZE;
        }
        return (int)ret;
    }
}